class Solution2 {

    boolean[][] row, col;
    boolean[][][] grid;

    public void solveSudoku(char[][] board) {
        row = new boolean[9][10];
        col = new boolean[9][10];
        grid = new boolean[3][3][10];

        //初始化
        for(int i = 0; i < 9; i++){
            for(int j = 0; j < 9; j++){
                if(board[i][j] != '.'){
                    int num = board[i][j] - '0';
                    row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = true;
                }
            }
        }

        dfs(board);
    }

    public boolean dfs(char[][] board){

        for(int i = 0; i < 9; i++){
            for(int j = 0; j < 9; j++){
                if(board[i][j] == '.'){
                    //填数
                    for(int num = 1; num <= 9; num++){
                        if(!row[i][num] && !col[j][num] && !grid[i / 3][j / 3][num]){
                            board[i][j] = (char)('0' + num);
                            row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = true;
                            if(dfs(board) == true) { return true;}  //告诉上层本次递归结果
                            //恢复现场
                            board[i][j] = '.';
                            row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = false;
                        }
                    }
                    return false;  //没有可以填的数
                }
            }
        }
        return true;  //没有 '.',直接返回
    }
}